package oj.oj_876;

import oj.ListNode;

/**
 * 链表的中间节点
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 * https://leetcode.cn/problems/middle-of-the-linked-list/description/
 */
// 时间复杂度：O(n)
// 空间复杂度：O(1)
public class Solution {
    private int sizeOf(ListNode head){//统计链表中元素的个数
        int count=0;
        for(ListNode cur=head;cur!=null;cur=cur.next){
            count++;
        }
        return count;
    }
    public ListNode middleNode(ListNode head) {
        ListNode cur=head;
        int size=sizeOf(head);
        for(int i=0;i<size/2;i++){//从头结点往后跳
            cur=cur.next;
        }
        return cur;
    }
}
